#include <stdio.h>
#include <stdlib.h>
#define Maxsize 10

// 顺序表结构
typedef struct
{
    int data[Maxsize];
    // last作用：标记最后一个含数值的元素在数组的第几个位置
    int last;
} SeqList;

// 函数声明
SeqList *init_SeqList(void);
int Insert_SeqList(SeqList *L, int i, int x);
int Delete_SeqList(SeqList *L, int i);
void merge(SeqList *A, SeqList *B, SeqList *C);

// 主函数
int main(void)
{
    // 定义该顺序表
    SeqList *L;

    // 初始化该顺序表
    L = init_SeqList();

    // 向顺序表插入数据
    Insert_SeqList(L, 1, 12);
    Insert_SeqList(L, 2, 14);
    Insert_SeqList(L, 3, 18);
    Insert_SeqList(L, 3, 6);
    // 删除顺序表的元素
    Delete_SeqList(L, 3);

#pragma region 合并线性表
    // 创造第二个线性表用于合并
    SeqList *L1;
    L1 = init_SeqList();
    Insert_SeqList(L1, 1, 11);
    Insert_SeqList(L1, 2, 15);
    Insert_SeqList(L1, 3, 19);
    // 创造合并后总线性表
    SeqList *LL;
    LL = init_SeqList();
    // 进行合并
    merge(L, L1, LL);
#pragma endregion

    return 0;
}

// 顺序表初始化
SeqList *init_SeqList()
{
    SeqList *p;
    p = (SeqList *)malloc(sizeof(SeqList));
    if (p)
    {
        p->last = -1;
        return p;
    }
    else
        return 0;
}

// 顺序表插入算法
int Insert_SeqList(SeqList *L, int i, int x)
{
    int j;
    // 检查该顺序表是否占满
    if (L->last == Maxsize - 1)
    {
        printf("表满");
        return 0;
    }
    // 检查插入位置的准确性
    if (i < 1 || i > L->last + 2)
    {
        printf("位置错");
        return 0;
    }
    // 每一个元素后移一位
    for (j = L->last; j >= i - 1; j--)
        L->data[j + 1] = L->data[j];
    // 插入数据
    L->data[i - 1] = x;
    // 尾元素后移
    L->last++;
    return 1;
}

// 顺序表删除算法
int Delete_SeqList(SeqList *L, int i)
{
    int j;
    // 检查删除位置的合法性
    if (i < 1 || i > L->last + 1)
    {
        printf("不存在第i个元素");
        return 0;
    }
    for (j = i; j <= L->last; j++)
        L->data[j - 1] = L->data[j];
    // 删除后最后一位数据不做处理，结尾指针前移
    L->last--;
    return 1;
}

// 顺序表合并算法
void merge(SeqList *A, SeqList *B, SeqList *C)
{
    int i = 0, j = 0, k = 0;
    // 将A\B中较小者复制到表C
    while (i <= A->last && j <= B->last)
    {
        if (A->data[i] < B->data[j])
            C->data[k++] = A->data[i++];
        else
            C->data[k++] = B->data[j++];
    }
    // 复制剩余元素
    while (i <= A->last)
    {
        C->data[k++] = A->data[i++];
    }
    while (j <= B->last)
    {
        C->data[k++] = B->data[j++];
    }
    C->last = k - 1;
}
